



<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      <meta http-equiv="x-ua-compatible" content="ie=edge">
      
        <meta name="description" content="Hrbust_ACM's Wiki">
      
      
        <link rel="canonical" href="https://hrbust-acm.online/Data_Structure/%E7%82%B9%E5%88%86%E6%B2%BB/">
      
      
        <meta name="author" content="Hrbust_Acmer">
      
      
        <meta name="lang:clipboard.copy" content="复制">
      
        <meta name="lang:clipboard.copied" content="已复制">
      
        <meta name="lang:search.language" content="ja">
      
        <meta name="lang:search.pipeline.stopwords" content="True">
      
        <meta name="lang:search.pipeline.trimmer" content="True">
      
        <meta name="lang:search.result.none" content="没有找到符合条件的结果">
      
        <meta name="lang:search.result.one" content="找到 1 个符合条件的结果">
      
        <meta name="lang:search.result.other" content="# 个符合条件的结果">
      
        <meta name="lang:search.tokenizer" content="[\uff0c\u3002]+">
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-4.6.3">
    
    
      
        <title>点分治 - Hrbust_ACM's Wiki</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/application.adb8469c.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/application-palette.a8b3c06d.css">
      
      
        
        
        <meta name="theme-color" content="#ef5350">
      
    
    
      <script src="../../assets/javascripts/modernizr.86422ebf.js"></script>
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto","Helvetica Neue",Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono","Courier New",Courier,monospace}</style>
      
    
    <link rel="stylesheet" href="../../assets/fonts/material-icons.css">
    
    
    
      
    
    
  </head>
  
    
    
    <body dir="ltr" data-md-color-primary="red" data-md-color-accent="blue">
  
    <svg class="md-svg">
      <defs>
        
        
          <svg xmlns="http://www.w3.org/2000/svg" width="416" height="448" viewBox="0 0 416 448" id="__github"><path fill="currentColor" d="M160 304q0 10-3.125 20.5t-10.75 19T128 352t-18.125-8.5-10.75-19T96 304t3.125-20.5 10.75-19T128 256t18.125 8.5 10.75 19T160 304zm160 0q0 10-3.125 20.5t-10.75 19T288 352t-18.125-8.5-10.75-19T256 304t3.125-20.5 10.75-19T288 256t18.125 8.5 10.75 19T320 304zm40 0q0-30-17.25-51T296 232q-10.25 0-48.75 5.25Q229.5 240 208 240t-39.25-2.75Q130.75 232 120 232q-29.5 0-46.75 21T56 304q0 22 8 38.375t20.25 25.75 30.5 15 35 7.375 37.25 1.75h42q20.5 0 37.25-1.75t35-7.375 30.5-15 20.25-25.75T360 304zm56-44q0 51.75-15.25 82.75-9.5 19.25-26.375 33.25t-35.25 21.5-42.5 11.875-42.875 5.5T212 416q-19.5 0-35.5-.75t-36.875-3.125-38.125-7.5-34.25-12.875T37 371.5t-21.5-28.75Q0 312 0 260q0-59.25 34-99-6.75-20.5-6.75-42.5 0-29 12.75-54.5 27 0 47.5 9.875t47.25 30.875Q171.5 96 212 96q37 0 70 8 26.25-20.5 46.75-30.25T376 64q12.75 25.5 12.75 54.5 0 21.75-6.75 42 34 40 34 99.5z"/></svg>
        
      </defs>
    </svg>
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" data-md-component="overlay" for="__drawer"></label>
    
      <a href="#k" tabindex="0" class="md-skip">
        跳转至
      </a>
    
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid">
    <div class="md-flex">
      <div class="md-flex__cell md-flex__cell--shrink">
        <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" aria-label="Hrbust_ACM's Wiki" class="md-header-nav__button md-logo">
          
            <i class="md-icon"></i>
          
        </a>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        <label class="md-icon md-icon--menu md-header-nav__button" for="__drawer"></label>
      </div>
      <div class="md-flex__cell md-flex__cell--stretch">
        <div class="md-flex__ellipsis md-header-nav__title" data-md-component="title">
          
            <span class="md-header-nav__topic">
              Hrbust_ACM's Wiki
            </span>
            <span class="md-header-nav__topic">
              
                点分治
              
            </span>
          
        </div>
      </div>
      <div class="md-flex__cell md-flex__cell--shrink">
        
          <label class="md-icon md-icon--search md-header-nav__button" for="__search"></label>
          
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" aria-label="search" name="query" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="query" data-md-state="active">
      <label class="md-icon md-search__icon" for="__search"></label>
      <button type="reset" class="md-icon md-search__icon" data-md-component="reset" tabindex="-1">
        &#xE5CD;
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="result">
          <div class="md-search-result__meta">
            键入以开始搜索
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
        
      </div>
      
        <div class="md-flex__cell md-flex__cell--shrink">
          <div class="md-header-nav__source">
            


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
          </div>
        </div>
      
    </div>
  </nav>
</header>
    
    <div class="md-container">
      
        
      
      
        

  

<nav class="md-tabs md-tabs--active" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../.." class="md-tabs__link">
          首页
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../S/DFS/" class="md-tabs__link">
          搜索
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" class="md-tabs__link">
          动态规划
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" class="md-tabs__link md-tabs__link--active">
          数据结构
        </a>
      
    </li>
  

      
        
  
  
    
    
  
  
    <li class="md-tabs__item">
      
        <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" class="md-tabs__link">
          图论
        </a>
      
    </li>
  

  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" class="md-tabs__link">
          字符串
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" class="md-tabs__link">
          计算几何
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../Others/Time/" class="md-tabs__link">
          附录
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
      
      <main class="md-main" role="main">
        <div class="md-main__inner md-grid" data-md-component="container">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" data-md-level="0">
  <label class="md-nav__title md-nav__title--site" for="__drawer">
    <a href="https://hrbust-acm.online" title="Hrbust_ACM's Wiki" class="md-nav__button md-logo">
      
        <i class="md-icon"></i>
      
    </a>
    Hrbust_ACM's Wiki
  </label>
  
    <div class="md-nav__source">
      


  

<a href="https://github.com/acm-hrbust-wiki/wiki/tree/" title="前往 Github 仓库" class="md-source" data-md-source="github">
  
    <div class="md-source__icon">
      <svg viewBox="0 0 24 24" width="24" height="24">
        <use xlink:href="#__github" width="24" height="24"></use>
      </svg>
    </div>
  
  <div class="md-source__repository">
    acm-hrbust-wiki/wiki
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-1" type="checkbox" id="nav-1">
    
    <label class="md-nav__link" for="nav-1">
      首页
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-1">
        首页
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../.." title="Getting Started" class="md-nav__link">
      Getting Started
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../home/" title="Wiki介绍" class="md-nav__link">
      Wiki介绍
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../faq/" title="如何使用" class="md-nav__link">
      如何使用
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-2" type="checkbox" id="nav-2">
    
    <label class="md-nav__link" for="nav-2">
      搜索
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-2">
        搜索
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DFS/" title="深度优先搜索" class="md-nav__link">
      深度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/BFS/" title="广度优先搜索" class="md-nav__link">
      广度优先搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/DeSearch/" title="双向搜索" class="md-nav__link">
      双向搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/Memory_Search/" title="记忆化搜索" class="md-nav__link">
      记忆化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alpha-beta%E5%89%AA%E6%9E%9D/" title="极大极小化搜索" class="md-nav__link">
      极大极小化搜索
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../S/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2/" title="启发式搜索" class="md-nav__link">
      启发式搜索
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-3" type="checkbox" id="nav-3">
    
    <label class="md-nav__link" for="nav-3">
      动态规划
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-3">
        动态规划
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E7%8A%B6%E5%8E%8BDP/" title="状态压缩DP" class="md-nav__link">
      状态压缩DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A0%91%E5%BD%A2DP/" title="树形 DP" class="md-nav__link">
      树形 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E5%8C%BA%E9%97%B4DP/" title="区间 DP" class="md-nav__link">
      区间 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%95%B0%E4%BD%8DDP/" title="数位 DP" class="md-nav__link">
      数位 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%A6%82%E7%8E%87DP/" title="概率 DP" class="md-nav__link">
      概率 DP
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../DP/%E6%9C%9F%E6%9C%9BDP/" title="期望 DP" class="md-nav__link">
      期望 DP
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      

  


  <li class="md-nav__item md-nav__item--active md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4" type="checkbox" id="nav-4" checked>
    
    <label class="md-nav__link" for="nav-4">
      数据结构
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-4">
        数据结构
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%841/" title="一维树状数组" class="md-nav__link">
      一维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%842/" title="二维树状数组" class="md-nav__link">
      二维树状数组
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../ST/" title="ST表" class="md-nav__link">
      ST表
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../RMQ/" title="RMQ" class="md-nav__link">
      RMQ
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-5" type="checkbox" id="nav-4-5">
    
    <label class="md-nav__link" for="nav-4-5">
      线段树
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-5">
        线段树
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../%E7%BA%BF%E6%AE%B5%E6%A0%91lazy/" title="线段树lazy标记" class="md-nav__link">
      线段树lazy标记
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6/" title="线段树区间合并" class="md-nav__link">
      线段树区间合并
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E6%89%AB%E6%8F%8F%E7%BA%BF/" title="扫描线" class="md-nav__link">
      扫描线
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-4-6" type="checkbox" id="nav-4-6">
    
    <label class="md-nav__link" for="nav-4-6">
      树链剖分
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-4-6">
        树链剖分
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../%E7%82%B9%E5%88%A8/" title="点剖" class="md-nav__link">
      点剖
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E8%BE%B9%E5%89%96/" title="边剖" class="md-nav__link">
      边剖
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E5%88%86%E5%9D%97/" title="分块算法" class="md-nav__link">
      分块算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../%E8%8E%AB%E9%98%9F/" title="莫队算法" class="md-nav__link">
      莫队算法
    </a>
  </li>

        
          
          
          

  


  <li class="md-nav__item md-nav__item--active">
    
    <input class="md-toggle md-nav__toggle" data-md-toggle="toc" type="checkbox" id="__toc">
    
    
      <label class="md-nav__link md-nav__link--active" for="__toc">
        点分治
      </label>
    
    <a href="./" title="点分治" class="md-nav__link md-nav__link--active">
      点分治
    </a>
    
      
<nav class="md-nav md-nav--secondary">
  
  
  
    <label class="md-nav__title" for="__toc">目录</label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#k" class="md-nav__link">
    例一、树上距离为 k 的点对是否存在.
  </a>
  
    <nav class="md-nav">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#1-rootgetroot" class="md-nav__link">
    1. 求树的重心函数Root.getroot()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#2-caldiscaldis" class="md-nav__link">
    2. 计算所有结点到根节点的距离函数 CalDis.caldis()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#3-sovledissovle" class="md-nav__link">
    3. 计算合法路径函数 SovleDis.sovle()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#4-dfzdfz" class="md-nav__link">
    4. 点分治函数 DFZ.dfz()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#5-dfzsolve" class="md-nav__link">
    5. 点分治调用 DFZ.solve()
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
        <li class="md-nav__item">
  <a href="#k_1" class="md-nav__link">
    例二、树上距离小于等于 K 的点对数量
  </a>
  
    <nav class="md-nav">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#1-rootgetroot_1" class="md-nav__link">
    1. 求树的重心函数 Root.getroot()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#2-caldiscaldis_1" class="md-nav__link">
    2. 计算所有结点到根节点的距离函数 CalDis.caldis()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#3-sovledissovle_1" class="md-nav__link">
    3. 计算合法路径函数 SovleDis.sovle()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#4-dfzdfz_1" class="md-nav__link">
    4. 点分治函数 DFZ.dfz()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#5-dfzsolve_1" class="md-nav__link">
    5. 点分治调用 DFZ.solve()
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
      
      
      
      
    </ul>
  
</nav>
    
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5">
    
    <label class="md-nav__link" for="nav-5">
      图论
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        图论
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-1" type="checkbox" id="nav-5-1">
    
    <label class="md-nav__link" for="nav-5-1">
      二分图
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-1">
        二分图
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" title="匈牙利算法" class="md-nav__link">
      匈牙利算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/KM%E7%AE%97%E6%B3%95/" title="KM 算法" class="md-nav__link">
      KM 算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-2" type="checkbox" id="nav-5-2">
    
    <label class="md-nav__link" for="nav-5-2">
      网络流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-2">
        网络流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/EK/" title="EK 算法" class="md-nav__link">
      EK 算法
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/Dinic/" title="Dinic+当前弧优化" class="md-nav__link">
      Dinic+当前弧优化
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/ISAP/" title="ISAP算法" class="md-nav__link">
      ISAP算法
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
          
          
          


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-5-3" type="checkbox" id="nav-5-3">
    
    <label class="md-nav__link" for="nav-5-3">
      费用流
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="2">
      <label class="md-nav__title" for="nav-5-3">
        费用流
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Graph/SPFA%E8%B4%B9%E7%94%A8%E6%B5%81/" title="SPFA 费用流" class="md-nav__link">
      SPFA 费用流
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      字符串
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        字符串
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/%E5%AD%97%E5%85%B8%E6%A0%91/" title="字典树" class="md-nav__link">
      字典树
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../String/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="AC自动机" class="md-nav__link">
      AC自动机
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7">
    
    <label class="md-nav__link" for="nav-7">
      计算几何
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        计算几何
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E7%82%B9%E7%A7%AF%E5%8F%89%E7%A7%AF%E7%9A%84%E8%BF%90%E7%94%A8/" title="点积叉积的运用" class="md-nav__link">
      点积叉积的运用
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%87%B8%E5%8C%85%E7%9A%84%E6%B1%82%E5%8F%96/" title="凸包的求取" class="md-nav__link">
      凸包的求取
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4/" title="半平面交" class="md-nav__link">
      半平面交
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Geometry/%E6%97%8B%E8%BD%AC%E5%8D%A1%E5%A3%B3/" title="旋转卡壳" class="md-nav__link">
      旋转卡壳
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-toggle md-nav__toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      附录
    </label>
    <nav class="md-nav" data-md-component="collapsible" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        附录
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/Time/" title="时间/空间复杂度" class="md-nav__link">
      时间/空间复杂度
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../Others/exem/" title="习题" class="md-nav__link">
      习题
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="toc">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    
<nav class="md-nav md-nav--secondary">
  
  
  
    <label class="md-nav__title" for="__toc">目录</label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#k" class="md-nav__link">
    例一、树上距离为 k 的点对是否存在.
  </a>
  
    <nav class="md-nav">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#1-rootgetroot" class="md-nav__link">
    1. 求树的重心函数Root.getroot()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#2-caldiscaldis" class="md-nav__link">
    2. 计算所有结点到根节点的距离函数 CalDis.caldis()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#3-sovledissovle" class="md-nav__link">
    3. 计算合法路径函数 SovleDis.sovle()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#4-dfzdfz" class="md-nav__link">
    4. 点分治函数 DFZ.dfz()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#5-dfzsolve" class="md-nav__link">
    5. 点分治调用 DFZ.solve()
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
        <li class="md-nav__item">
  <a href="#k_1" class="md-nav__link">
    例二、树上距离小于等于 K 的点对数量
  </a>
  
    <nav class="md-nav">
      <ul class="md-nav__list">
        
          <li class="md-nav__item">
  <a href="#1-rootgetroot_1" class="md-nav__link">
    1. 求树的重心函数 Root.getroot()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#2-caldiscaldis_1" class="md-nav__link">
    2. 计算所有结点到根节点的距离函数 CalDis.caldis()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#3-sovledissovle_1" class="md-nav__link">
    3. 计算合法路径函数 SovleDis.sovle()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#4-dfzdfz_1" class="md-nav__link">
    4. 点分治函数 DFZ.dfz()
  </a>
  
</li>
        
          <li class="md-nav__item">
  <a href="#5-dfzsolve_1" class="md-nav__link">
    5. 点分治调用 DFZ.solve()
  </a>
  
</li>
        
      </ul>
    </nav>
  
</li>
      
      
      
      
      
    </ul>
  
</nav>
                  </div>
                </div>
              </div>
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                  <a href="https://github.com/acm-hrbust-wiki/wiki/tree/docs/Data_Structure/点分治.md" title="编辑此页" class="md-icon md-content__icon">&#xE3C9;</a>
                
                
                  <h1>点分治</h1>
                
                <h2 id="k">例一、树上距离为 k 的点对是否存在.<a class="headerlink" href="#k" title="Permanent link">&para;</a></h2>
<p>///洛谷 P3806 给定一颗 n 个结点的无根树,有 m 次询问,每次询问树上距离为 k 的点对是否存在.</p>
<p><strong>思想:</strong>  用桶记录路径,判断是否存在距离为 k 的点对</p>
<p><strong>使用方法:</strong>  调用 <code>DFZ.sovle()</code>函数后答案存入 <code>ans[]</code>数组</p>
<p><strong>模块说明:</strong></p>
<h4 id="1-rootgetroot">1. 求树的重心函数<code>Root.getroot()</code><a class="headerlink" href="#1-rootgetroot" title="Permanent link">&para;</a></h4>
<p>输入<strong>:</strong> 使用 <code>Root.getroot(u,fa,sum)</code>,<code>u</code>为当前结点,<code>fa</code> 为<code>u</code>结点的父亲结点,<code>sum</code>是当前连通块的大小 </p>
<p>输出: 返回重心结点编号 <code>rt</code></p>
<h4 id="2-caldiscaldis">2. 计算所有结点到根节点的距离函数 <code>CalDis.caldis()</code><a class="headerlink" href="#2-caldiscaldis" title="Permanent link">&para;</a></h4>
<p>输入：使用 <code>CalDis.caldis(int u,int fa)</code>,<code>u</code> 为当前结点,<code>fa</code> 为 <code>u</code> 结点的父亲结点</p>
<p>输出<strong>:</strong> 得到<code>di[]</code>数组,<code>dis[]</code>数组大小为<code>tp</code>,存有所有基本路径的长度,还有 <code>dis[]</code>数组,存的是结点 <code>u</code>到当前根节点的长度</p>
<h4 id="3-sovledissovle">3. 计算合法路径函数 SovleDis.sovle()<a class="headerlink" href="#3-sovledissovle" title="Permanent link">&para;</a></h4>
<p>输入: 使用 <code>SovleDis.sovle(int u)</code>,<code>u</code> 为当前结点 </p>
<p>输出: 得到当前 <code>ans[]</code>数组,,存有每次更新的答案信息 </p>
<h4 id="4-dfzdfz">4. 点分治函数 DFZ.dfz()<a class="headerlink" href="#4-dfzdfz" title="Permanent link">&para;</a></h4>
<p>输入: 使用 <code>DFZ.dfz(int u)</code>,<code>u</code> 为当前结点 </p>
<p>输出: 递归各结点 </p>
<h4 id="5-dfzsolve">5. 点分治调用 DFZ.solve()<a class="headerlink" href="#5-dfzsolve" title="Permanent link">&para;</a></h4>
<p>输入<strong>:</strong> 无</p>
<p>输出: 得到最终 <code>ans[]</code>数组,存有答案信息</p>
<table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">amn</span> <span class="o">=</span> <span class="mf">1e5</span> <span class="o">+</span> <span class="mi">5</span><span class="p">,</span> <span class="n">inf</span> <span class="o">=</span> <span class="mf">1e9</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">K</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="c1">///链式前向星存图</span>
<span class="kt">int</span> <span class="n">head</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">etot</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">edge</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">nxt</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">;</span>
<span class="p">}</span> <span class="n">eg</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="kt">void</span> <span class="nf">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">eg</span><span class="p">[</span><span class="o">++</span><span class="n">etot</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">};</span>
    <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">etot</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">vis</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="c1">///求树的重心</span>
<span class="k">class</span> <span class="nc">Root</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">siz</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">maxt</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">rt</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">calsiz</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">||</span> <span class="n">v</span> <span class="o">==</span> <span class="n">fa</span><span class="p">)</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="mi">48</span> <span class="n">calsiz</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">sum</span><span class="p">);</span>
            <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+=</span> <span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span>
            <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span>
        <span class="p">}</span>
        <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">sum</span> <span class="o">-</span> <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">maxt</span><span class="p">[</span><span class="n">rt</span><span class="p">])</span>
            <span class="n">rt</span> <span class="o">=</span> <span class="n">u</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">getroot</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">rt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="n">maxt</span><span class="p">[</span><span class="n">rt</span><span class="p">]</span> <span class="o">=</span> <span class="n">inf</span><span class="p">;</span>
        <span class="n">calsiz</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">fa</span><span class="p">,</span> <span class="n">sum</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///求基本路径 dis</span>
<span class="k">class</span> <span class="nc">CalDis</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">dis</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">di</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">tp</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">caldis</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">&gt;</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="mf">1e7</span><span class="p">)</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="n">di</span><span class="p">[</span><span class="o">++</span><span class="n">tp</span><span class="p">]</span> <span class="o">=</span> <span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">];</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span> <span class="n">w</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">||</span> <span class="n">v</span> <span class="o">==</span> <span class="n">fa</span><span class="p">)</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">dis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+</span> <span class="n">w</span><span class="p">;</span>
            <span class="n">caldis</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">tp</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="n">dis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">w</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///判断路径</span>
<span class="kt">bool</span> <span class="n">jg</span><span class="p">[(</span><span class="kt">int</span><span class="p">)</span><span class="mf">1e7</span> <span class="o">+</span> <span class="mi">1</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">ans</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="k">class</span> <span class="nc">SovleDis</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">CalDis</span> <span class="n">cd</span><span class="p">;</span>
    <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">bk</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">sovle</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">jg</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">bk</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span> <span class="n">w</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">;</span>
            <span class="mi">49</span> <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span>
            <span class="n">cd</span><span class="p">.</span><span class="n">init</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">);</span>
            <span class="n">cd</span><span class="p">.</span><span class="n">caldis</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">);</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">cd</span><span class="p">.</span><span class="n">tp</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span>
                <span class="p">{</span>
                    <span class="k">if</span> <span class="p">(</span><span class="n">K</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
                        <span class="n">ans</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">+=</span> <span class="n">jg</span><span class="p">[</span><span class="n">K</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">-</span> <span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">j</span><span class="p">]];</span>
                <span class="p">}</span>
            <span class="p">}</span>
            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">cd</span><span class="p">.</span><span class="n">tp</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">jg</span><span class="p">[</span><span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">j</span><span class="p">]]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
                <span class="n">bk</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">bk</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
        <span class="p">{</span>
            <span class="n">jg</span><span class="p">[</span><span class="n">bk</span><span class="p">.</span><span class="n">front</span><span class="p">()]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
            <span class="n">bk</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///点分治</span>
<span class="k">class</span> <span class="nc">DFZ</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">Root</span> <span class="n">rt</span><span class="p">;</span>
    <span class="n">SovleDis</span> <span class="n">s</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">dfz</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">s</span><span class="p">.</span><span class="n">sovle</span><span class="p">(</span><span class="n">u</span><span class="p">);</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">rt</span><span class="p">.</span><span class="n">getroot</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">rt</span><span class="p">.</span><span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span>
            <span class="n">dfz</span><span class="p">(</span><span class="n">rt</span><span class="p">.</span><span class="n">rt</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">sovle</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">rt</span><span class="p">.</span><span class="n">getroot</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span>
        <span class="n">dfz</span><span class="p">(</span><span class="n">rt</span><span class="p">.</span><span class="n">rt</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">DFZ</span> <span class="n">df</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">;</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">n</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">m</span><span class="p">);</span>
    <span class="mi">50</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d%d%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">c</span><span class="p">);</span>
        <span class="n">add</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">);</span>
        <span class="n">add</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">c</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">K</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="n">df</span><span class="p">.</span><span class="n">sovle</span><span class="p">();</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">ans</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&quot;AYE</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
        <span class="k">else</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&quot;NAY</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<h2 id="k_1">例二、树上距离小于等于 K 的点对数量<a class="headerlink" href="#k_1" title="Permanent link">&para;</a></h2>
<p>///洛谷 P4178 给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。 </p>
<p><strong>思想:</strong>用容斥和双指针记录路径,计算距离小于等于 k 的点对有多少个.</p>
<p><strong>使用方法:</strong> 调用 DFZ.sovle()函数后答案存入 ans</p>
<p><strong>模块说明:</strong></p>
<h4 id="1-rootgetroot_1">1. 求树的重心函数 Root.getroot()<a class="headerlink" href="#1-rootgetroot_1" title="Permanent link">&para;</a></h4>
<p>输入: 使用 Root.getroot(u,fa,sum),u 为当前结点,fa 为u结点的父亲结点,sum 是当前连通块的大 小 </p>
<p>输出: 返回重心结点编号 rt</p>
<h4 id="2-caldiscaldis_1">2. 计算所有结点到根节点的距离函数 CalDis.caldis()<a class="headerlink" href="#2-caldiscaldis_1" title="Permanent link">&para;</a></h4>
<p>输入: 使用 CalDis.caldis(int u,int fa),u 为当前结点,fa 为 u 结点的父亲结点</p>
<p>输出: 得到 di[]数组,di[]数组大小为 tp,存有所有基本路径的长度,还有 dis[]数组,存的是结点 u 到当前根节点的长度</p>
<h4 id="3-sovledissovle_1">3. 计算合法路径函数 SovleDis.sovle()<a class="headerlink" href="#3-sovledissovle_1" title="Permanent link">&para;</a></h4>
<p>输入: 使用 SovleDis.sovle(int u,int fa,int w),u 为当前结点,fa 为 u 结点的父亲结点,w 为 fa 到 u 的 边权 </p>
<p>输出: 得到当前 ans,存有每次更新的答案信息</p>
<h4 id="4-dfzdfz_1">4. 点分治函数 DFZ.dfz()<a class="headerlink" href="#4-dfzdfz_1" title="Permanent link">&para;</a></h4>
<p>输入: 使用 DFZ.dfz(int u),u 为当前结点 </p>
<p>输出: 递归各结点</p>
<h4 id="5-dfzsolve_1">5. 点分治调用 DFZ.solve()<a class="headerlink" href="#5-dfzsolve_1" title="Permanent link">&para;</a></h4>
<p>输入: 无 </p>
<p>输出: 得到最终 ans,存有答案信息 </p>
<table class="codehilitetable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span>  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138</pre></div></td><td class="code"><div class="codehilite"><pre><span></span><code><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">amn</span> <span class="o">=</span> <span class="mf">1e5</span> <span class="o">+</span> <span class="mi">5</span><span class="p">,</span> <span class="n">inf</span> <span class="o">=</span> <span class="mf">1e9</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">K</span><span class="p">;</span>
<span class="c1">///链式前向星存图</span>
<span class="kt">int</span> <span class="n">head</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">etot</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">edge</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">nxt</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">;</span>
<span class="p">}</span> <span class="n">eg</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="kt">void</span> <span class="nf">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">eg</span><span class="p">[</span><span class="o">++</span><span class="n">etot</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">v</span><span class="p">,</span> <span class="n">w</span><span class="p">};</span>
    <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">etot</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">vis</span><span class="p">[</span><span class="n">amn</span><span class="p">];</span>
<span class="c1">///求树的重心</span>
<span class="k">class</span> <span class="nc">Root</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">siz</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">maxt</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">rt</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">calsiz</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">||</span> <span class="n">v</span> <span class="o">==</span> <span class="n">fa</span><span class="p">)</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">calsiz</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">sum</span><span class="p">);</span>
            <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+=</span> <span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span>
            <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span>
        <span class="p">}</span>
        <span class="mi">52</span> <span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">sum</span> <span class="o">-</span> <span class="n">siz</span><span class="p">[</span><span class="n">u</span><span class="p">]);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">maxt</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">maxt</span><span class="p">[</span><span class="n">rt</span><span class="p">])</span>
            <span class="n">rt</span> <span class="o">=</span> <span class="n">u</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">getroot</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">,</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">rt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="n">maxt</span><span class="p">[</span><span class="n">rt</span><span class="p">]</span> <span class="o">=</span> <span class="n">inf</span><span class="p">;</span>
        <span class="n">calsiz</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">fa</span><span class="p">,</span> <span class="n">sum</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///求基本路径 dis</span>
<span class="k">class</span> <span class="nc">CalDis</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">dis</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">di</span><span class="p">[</span><span class="n">amn</span><span class="p">],</span> <span class="n">tp</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">caldis</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">K</span><span class="p">)</span>
            <span class="k">return</span><span class="p">;</span>
        <span class="n">di</span><span class="p">[</span><span class="o">++</span><span class="n">tp</span><span class="p">]</span> <span class="o">=</span> <span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">];</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span> <span class="n">w</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">||</span> <span class="n">v</span> <span class="o">==</span> <span class="n">fa</span><span class="p">)</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">dis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">dis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+</span> <span class="n">w</span><span class="p">;</span>
            <span class="n">caldis</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">tp</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="n">dis</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">w</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///判断路径</span>
<span class="kt">int</span> <span class="n">ans</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">SovleDis</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">CalDis</span> <span class="n">cd</span><span class="p">;</span>
    <span class="kt">int</span> <span class="nf">sovle</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">,</span> <span class="kt">int</span> <span class="n">fa</span><span class="p">,</span> <span class="kt">int</span> <span class="n">w</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">cd</span><span class="p">.</span><span class="n">init</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">w</span><span class="p">);</span>
        <span class="n">cd</span><span class="p">.</span><span class="n">caldis</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">fa</span><span class="p">);</span>
        <span class="n">sort</span><span class="p">(</span><span class="n">cd</span><span class="p">.</span><span class="n">di</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">cd</span><span class="p">.</span><span class="n">di</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">cd</span><span class="p">.</span><span class="n">tp</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">cd</span><span class="p">.</span><span class="n">tp</span><span class="p">,</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">l</span><span class="p">]</span> <span class="o">+</span> <span class="n">cd</span><span class="p">.</span><span class="n">di</span><span class="p">[</span><span class="n">r</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">K</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">ans</span> <span class="o">+=</span> <span class="n">r</span> <span class="o">-</span> <span class="n">l</span><span class="p">;</span>
                <span class="n">l</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">else</span>
                <span class="n">r</span><span class="o">--</span><span class="p">;</span>
            <span class="mi">53</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="c1">///点分治</span>
<span class="k">class</span> <span class="nc">DFZ</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">Root</span> <span class="n">rt</span><span class="p">;</span>
    <span class="n">SovleDis</span> <span class="n">s</span><span class="p">;</span>
    <span class="kt">void</span> <span class="nf">dfz</span><span class="p">(</span><span class="kt">int</span> <span class="n">u</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">vis</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="n">ans</span> <span class="o">+=</span> <span class="n">s</span><span class="p">.</span><span class="n">sovle</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">head</span><span class="p">[</span><span class="n">u</span><span class="p">];</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">nxt</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">v</span><span class="p">,</span> <span class="n">w</span> <span class="o">=</span> <span class="n">eg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">w</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">vis</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
                <span class="k">continue</span><span class="p">;</span>
            <span class="n">ans</span> <span class="o">-=</span> <span class="n">s</span><span class="p">.</span><span class="n">sovle</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">w</span><span class="p">);</span>
            <span class="n">rt</span><span class="p">.</span><span class="n">getroot</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">u</span><span class="p">,</span> <span class="n">rt</span><span class="p">.</span><span class="n">siz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span>
            <span class="n">dfz</span><span class="p">(</span><span class="n">rt</span><span class="p">.</span><span class="n">rt</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">sovle</span><span class="p">()</span>
    <span class="p">{</span>
        <span class="n">rt</span><span class="p">.</span><span class="n">getroot</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span>
        <span class="n">dfz</span><span class="p">(</span><span class="n">rt</span><span class="p">.</span><span class="n">rt</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">DFZ</span> <span class="n">df</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">;</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">n</span><span class="p">);</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d%d%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">c</span><span class="p">);</span>
        <span class="n">add</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">);</span>
        <span class="n">add</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">c</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">K</span><span class="p">);</span>
    <span class="n">df</span><span class="p">.</span><span class="n">sovle</span><span class="p">();</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">ans</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
</td></tr></table>

<p>整理人：计 18-8 蒙晟维</p>
                
                  
                
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
    <div class="md-footer-nav">
      <nav class="md-footer-nav__inner md-grid">
        
          <a href="../%E8%8E%AB%E9%98%9F/" title="莫队算法" class="md-flex md-footer-nav__link md-footer-nav__link--prev" rel="prev">
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-back md-footer-nav__button"></i>
            </div>
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  上一页
                </span>
                莫队算法
              </span>
            </div>
          </a>
        
        
          <a href="../../Graph/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/" title="匈牙利算法" class="md-flex md-footer-nav__link md-footer-nav__link--next" rel="next">
            <div class="md-flex__cell md-flex__cell--stretch md-footer-nav__title">
              <span class="md-flex__ellipsis">
                <span class="md-footer-nav__direction">
                  下一页
                </span>
                匈牙利算法
              </span>
            </div>
            <div class="md-flex__cell md-flex__cell--shrink">
              <i class="md-icon md-icon--arrow-forward md-footer-nav__button"></i>
            </div>
          </a>
        
      </nav>
    </div>
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
        powered by
        <a href="https://www.mkdocs.org" target="_blank" rel="noopener">MkDocs</a>
        and
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs</a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/application.c33a9706.js"></script>
      
        
        
          
          <script src="../../assets/javascripts/lunr/lunr.stemmer.support.js"></script>
          
            
              
                <script src="../../assets/javascripts/lunr/tinyseg.js"></script>
              
              
                <script src="../../assets/javascripts/lunr/lunr.ja.js"></script>
              
            
          
          
        
      
      <script>app.initialize({version:"1.1",url:{base:"../.."}})</script>
      
        <script src="https://cdnjs.loli.net/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>